package leetcode.dp;

import java.util.stream.IntStream;

public class PartitionEqualSubsetSum416 {
    class Solution1 {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = IntStream.of(nums).sum();
            if ((sum % 2) != 0) {
                return false;
            }
            boolean[][] dp = new boolean[nums.length + 1][sum / 2 + 1];
            dp[0][0] = true;
            for (int i = 1; i <= nums.length; i++) {
                for (int j = 0; j <= sum / 2; j++) {
                    if (j < nums[i - 1]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                    }
                }
            }
           return dp[nums.length][sum / 2];
        }
    }

    class Solution2 {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = IntStream.of(nums).sum();
            if ((sum % 2) != 0) {
                return false;
            }
            boolean[] dp = new boolean[sum / 2 + 1];
            dp[0] = true;
            for (int i = 1; i <= nums.length; i++) {
                for (int j = sum / 2; j >= nums[i - 1]; j++) {
                   dp[j] = dp[j] || dp[j - nums[i - 1]];
                }
            }
            return dp[sum / 2];
        }
    }
}